import java.util.HashMap;
import java.util.Map;

/**
 * @author kaho
 * @since 2021/3/17
 */
public class _3_无重复字符的最长子串 {

    /**
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring1(String s) {
        if (s.length()<=1) {
            return s.length();
        }
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int start = 0, end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(start, map.get(c));
            }
            max = Math.max(max, end-start+1);
            map.put(c, end+1);
        }
        return max;
    }


    public static int lengthOfLongestSubstring(String s) {
        if (s.length()<=1) {
            return s.length();
        }
        int[] dp = new int[s.length()];
        dp[0] = 1;

        for (int i = 1; i < s.length(); i++) {
            int k = i-1;
            boolean r = true;
            for (int j = 0; j < dp[i-1]; j++) {
                if (s.charAt(k)== s.charAt(i)) {
                    r = false;
                    dp[i] = i-k;
                }
                k--;
            }
            if (r) {
                dp[i] = dp[i-1]+1;
            }
        }
        int max = 0;
        for (int i : dp) {
            if (i>max) {
                max = i;
            }
        }
        return max;
    }

    public static void main(String[] args) {
//        int abcabcbb = lengthOfLongestSubstring1("pwwkew");
        int abcabcbb = lengthOfLongestSubstring1("abcabcbb");
    }
}
